<!DOCTYPE html>
<html lang="zh">

<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <title>
    
    绪论 - DSRBLOG
    
  </title>
  

  
  
  <link href="atom.xml" rel="alternate" title="DSRBLOG" type="application/atom+xml">
  <link rel="stylesheet" href="asset/css/style.min.css">
  <link rel="stylesheet" href="asset/css/doc.css">
  <script src="asset/app.js"></script>


</head>

<body> <section class="ct-body">
	<div class="container">
		<div class="columns is-variable bd-klmn-columns is-4 is-centered">
			<div class="column is-four-fifths">
				<div class="post-body single-content">
					
					<h1 class="title">
						绪论
					</h1>


					<div class="media">
						
						
						<div class="media-content">
							<div class="content">
								<p>
									<span class="date">2022/02/19 02:24 上午</span>
									

									

									<br />
									<span class="tran-tags">Tags:</span>&nbsp;
									
									<a class="tag is-link is-light">#数据结构与算法</a>
									

								</p>
							</div>
						</div>

					</div>
				</div>
				<article class="markdown-body single-content">
					<h2><a id="%E4%BB%80%E4%B9%88%E6%98%AF%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>什么是数据结构</h2>
<h3><a id="q1%E5%A6%82%E4%BD%95%E9%87%87%E7%94%A8%E8%AE%A1%E7%AE%97%E6%9C%BA%E8%A7%A3%E5%86%B3%E9%97%AE%E9%A2%98" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Q1 如何采用计算机解决问题</h3>
<ul>
<li>从具体问题抽象出一个适当的数学模型</li>
<li>为该模型设计算法</li>
<li>编程，测试、调整直至得到最终解答</li>
</ul>
<p>寻求数学模型的实质：分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述</p>
<h3><a id="q2%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%A7%A3%E5%86%B3%E4%BB%80%E4%B9%88%E6%A0%B7%E7%9A%84%E9%97%AE%E9%A2%98" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Q2 数据结构解决什么样的问题</h3>
<p>数据结构研究非数值计算的程序设计问题中，计算机的<strong>操作对象</strong>，以及它们之间的<strong>关系</strong>和<strong>操作</strong>等</p>
<h3><a id="q3%E3%80%8A%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E3%80%8B%E8%AF%BE%E7%A8%8B%E4%BB%8B%E7%BB%8D" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Q3 《数据结构》课程介绍</h3>
<p>介于数学、计算机硬件和计算机软件<strong>三者之间</strong>的一门核心课程</p>
<h2><a id="%E5%9F%BA%E6%9C%AC%E6%A6%82%E5%BF%B5%E5%92%8C%E6%9C%AF%E8%AF%AD" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>基本概念和术语</h2>
<h3><a id="q1%E4%BB%80%E4%B9%88%E6%98%AF%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Q1 什么是数据结构</h3>
<p>数据结构是相互之间存在<strong>一种或多种特定关系</strong>的数据元素的集合，表示为：<br />
<img src="media/16452086895937/16471100674244.jpg" alt="" /></p>
<p><strong>D：</strong> 元素有限集（数据）<br />
<strong>S：</strong> 关系有限集（结构）</p>
<h4><a id="%E6%9C%AF%E8%AF%AD" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>术语</h4>
<h5><a id="%E6%95%B0%E6%8D%AE%EF%BC%88data%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>数据（Data）</h5>
<p>所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）</p>
<h5><a id="%E6%95%B0%E6%8D%AE%E5%AF%B9%E8%B1%A1%EF%BC%88data-object%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>数据对象（Data object）</h5>
<p>性质相同的数据元素的集合，是数据的一个子集，是<strong>数据元素</strong>构成的集合</p>
<h5><a id="%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0%EF%BC%88data-element%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>数据元素（Data element）</h5>
<p>数据的<strong>基本单位</strong>，用于完整地描述一个对象，具有完整确定的实际意义（又称元素、结点、顶点、记录等）</p>
<h5><a id="%E6%95%B0%E6%8D%AE%E9%A1%B9%EF%BC%88data-item%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>数据项（Data item）</h5>
<p>构成数据元素的项目，是<strong>具有独立含义、不可分割</strong>的最小标识单位（又称字段、域、属性等）</p>
<h5><a id="%E4%B8%BE%E4%BE%8B" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>举例</h5>
<table>
<thead>
<tr>
<th>数据对象</th>
<th>数据元素</th>
<th>数据项</th>
</tr>
</thead>
<tbody>
<tr>
<td>班级通讯录</td>
<td>个人记录</td>
<td>姓名、年龄...</td>
</tr>
</tbody>
</table>
<h3><a id="q2%E5%AD%A6%E4%B9%A0%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E6%9C%89%E4%BB%80%E4%B9%88%E7%94%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Q2 学习数据结构有什么用</h3>
<p>计算机内的数值运算依靠方程式，而非数值运算（如表、数、图等）则依靠数据结构</p>
<h3><a id="q3%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E6%B6%B5%E7%9B%96%E7%9A%84%E4%B8%BB%E8%A6%81%E5%86%85%E5%AE%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Q3 数据结构涵盖的主要内容</h3>
<pre class="line-numbers"><code class="language-mermaid">graph LR
Data_structure(数据结构)--- Logical_structure(逻辑结构)
Data_structure---Physical_storage_structure(&quot;物理(存储)结构&quot;)
Data_structure---Data_operation(数据运算)

Logical_structure---collection_structure(集合结构)
Logical_structure---Linear_structure(&quot;线性结构(线性表、栈、队、串、数组)&quot;)
Logical_structure---Nonlinear_structure(非线性结构)

Nonlinear_structure---Tree_structure(树结构)
Nonlinear_structure---Graph_structure(图结构)

Physical_storage_structure---Sequential_structure(顺序结构)
Physical_storage_structure---Chain_structure(链式结构)
Physical_storage_structure---Index_structure(索引结构)
Physical_storage_structure---Hash_structure(散列结构)

Data_operation---Insert(插入运算)
Data_operation---Delete(删除运算)
Data_operation---Modify(修改运算)
Data_operation---Find(查找运算)
Data_operation---Sort(排序运算)
</code></pre>
<h4><a id="%E6%95%B0%E6%8D%AE%E7%9A%84%E9%80%BB%E8%BE%91%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>数据的逻辑结构</h4>
<p>指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的，可细分为以下4种：</p>
<table>
<thead>
<tr>
<th>类型</th>
<th>关系</th>
<th>结构</th>
</tr>
</thead>
<tbody>
<tr>
<td>集合结构</td>
<td>仅同属一个集合</td>
<td></td>
</tr>
<tr>
<td><strong>线性</strong>结构</td>
<td>一对一（1 : 1）</td>
<td>线性</td>
</tr>
<tr>
<td><strong>树状</strong>结构</td>
<td>一对多（1 : n）</td>
<td>非线性</td>
</tr>
<tr>
<td><strong>图</strong>结构</td>
<td>多对多（m : n）</td>
<td>非线性</td>
</tr>
</tbody>
</table>
<h4><a id="%E6%95%B0%E6%8D%AE%E7%9A%84%E7%89%A9%E7%90%86%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>数据的物理结构</h4>
<p>物理结构页脚存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像），它依赖于计算机，可分为4类：</p>
<table>
<thead>
<tr>
<th>结构</th>
<th>优点</th>
<th>缺点</th>
</tr>
</thead>
<tbody>
<tr>
<td>顺序结构</td>
<td>紧密排列，存储密度大</td>
<td>插入、删除运算效率低</td>
</tr>
<tr>
<td>链式结构</td>
<td>插入、删除运算效率高，动态分配空间灵活</td>
<td>存储密度低，额外的空间开销</td>
</tr>
<tr>
<td>索引结构</td>
<td>不需要预留物理块，满足增长、插入、删除的要求</td>
<td>索引表本身存在额外空间开销</td>
</tr>
<tr>
<td>散列结构</td>
<td></td>
<td></td>
</tr>
</tbody>
</table>
<h4><a id="%E6%95%B0%E6%8D%AE%E7%9A%84%E8%BF%90%E7%AE%97" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>数据的运算</h4>
<p>在数据的<strong>逻辑结构上定义的操作算法</strong>，它在<strong>数据的存储结构上实现</strong>，最常用的数据运算有5种：</p>
<ul>
<li>插入运算</li>
<li>删除运算</li>
<li>修改运算</li>
<li>查找运算</li>
<li>排序运算</li>
</ul>
<h2><a id="%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E7%9A%84%E8%A1%A8%E7%A4%BA%E5%92%8C%E5%AE%9E%E7%8E%B0" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>抽象数据类型的表示和实现</h2>
<h3><a id="q1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E4%B8%8E%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E7%9A%84%E5%8C%BA%E5%88%AB" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Q1 数据类型与抽象数据类型的区别</h3>
<h4><a id="%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>数据类型</h4>
<p>由语言定义，类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算，是一个值的集合与定义在该值上的一组操作的总称</p>
<p><strong>如：</strong> int、char、double、float...</p>
<h4><a id="%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>抽象数据类型</h4>
<p>一般由用户定义，用以表示应用问题的数据模型，以及定义在这个模型上的一组操作的总称，它由数据对象、数据对象上关系的集合，以及对数据对象的基本操作的集合构成</p>
<p>它与数据类型实质上是一个概念，但其特证是使用与实现分离，实行封装和信息屏蔽（独立于计算机）</p>
<p><strong>抽象数据类型</strong>可以用以下的三元数来表示：<code>ADT = (D, S, P)</code><br />
<strong>D：</strong> 数据对象<br />
<strong>S：</strong> D上的关系集<br />
<strong>P：</strong> D上的操作集</p>
<h5><a id="adt%E5%B8%B8%E7%94%A8%E5%AE%9A%E4%B9%89%E6%A0%BC%E5%BC%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>ADT常用定义格式</h5>
<pre class="line-numbers"><code class="language-plain_text">ADT 抽象数据类型名{
    数据对象:&lt;数据对象的定义&gt;
    数据关系:&lt;数据关系的定义&gt;
    基本操作:&lt;基本操作的定义&gt;
} ADT 抽象数据类型名
</code></pre>
<h3><a id="q2%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E5%A6%82%E4%BD%95%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Q2 抽象数据类型如何定义</h3>
<pre class="line-numbers"><code class="language-c">ADT Triplet {
    数据对象:D = {e1, e2, e3 | e1, e2, e3 ∈ ElemSet（定义了关系运算的某个集合）}//e1, e2, e3同属一个集合
    数据关系:R1 = {&lt;e1, e2&gt;, &lt;e2, e3&gt;}//e1, e2, e3拥有次序关系，不能打乱
    基本操作:
        InitTriplet(&amp;T, v1, v2, v3)
            //操作结果：构造了三元组T，元素e1, e2和e3分别被赋以参数v1, v2和v3的值
        DestroyTriplet(&amp;T)
            //操作结果：三元组T被销毁
        Get(T, i, &amp;e)
            //初始条件：三元组T已存在，1≤i≤3
            //操作结果：用e返回T的第i元的值
        Put(&amp;T, i, e)
            //初始条件：三元组T已存在，1≤i≤3
            //操作结果：改变T的第i元的值为e
} ADT Triplet 
</code></pre>
<h3><a id="q3%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E5%A6%82%E4%BD%95%E8%A1%A8%E7%A4%BA%E5%92%8C%E5%AE%9E%E7%8E%B0" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Q3 抽象数据类型如何表示和实现</h3>
<ul>
<li>
<p>抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现</p>
</li>
<li>
<p>利用已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作</p>
</li>
</ul>
<h2><a id="%E7%AE%97%E6%B3%95%E5%92%8C%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>算法和算法分析</h2>
<h3><a id="q1%E4%BB%80%E4%B9%88%E6%98%AF%E7%AE%97%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Q1 什么是算法</h3>
<p>算法是解决某一特定类型问题的一段代码（有限序列），是一系列输入转换为输出的计算步骤</p>
<h4><a id="%E7%AE%97%E6%B3%95%E7%9A%845%E4%B8%AA%E5%9F%BA%E6%9C%AC%E7%89%B9%E6%80%A7" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>算法的5个基本特性</h4>
<table>
<thead>
<tr>
<th>特性</th>
<th>解释</th>
</tr>
</thead>
<tbody>
<tr>
<td>有穷性</td>
<td>算法需要经过有限次的计算得出计算，并且在有限的时间内完成</td>
</tr>
<tr>
<td>确定性</td>
<td>在相同输入环境下必须<strong>输出明确的结果</strong>，不会产生二义性</td>
</tr>
<tr>
<td>可行性</td>
<td>必须可以在<strong>当前软硬件环境</strong>下运行</td>
</tr>
<tr>
<td>输入</td>
<td>可以存在<strong>零个或多个</strong>输入</td>
</tr>
<tr>
<td>输出</td>
<td>必须存在<strong>一个或多个</strong>输出</td>
</tr>
</tbody>
</table>
<h3><a id="q2%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E7%9A%84%E8%A6%81%E6%B1%82" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Q2 算法设计的要求</h3>
<table>
<thead>
<tr>
<th>特性</th>
<th>解释</th>
</tr>
</thead>
<tbody>
<tr>
<td>正确性</td>
<td>在合理的数据输入下，能够在有限的运行时间内得到<strong>正确的结果</strong></td>
</tr>
<tr>
<td>可读性</td>
<td>应<strong>便于人们理解</strong>和相互交流，其次才是机器的可执行性</td>
</tr>
<tr>
<td>健壮性</td>
<td>当输入的数据非法时，能适当的作出正确的反应或相应处理</td>
</tr>
<tr>
<td>高效性</td>
<td>包括时间和空间两个方面，执行效率越高、占用空间越低越好</td>
</tr>
</tbody>
</table>
<h3><a id="q3%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%A6%82%E4%BD%95%E8%A1%A8%E7%A4%BA" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Q3 时间复杂度如何表示</h3>
<p>算法执行时间需要通过该算法编制的程序在计算机上运行时所消耗的时间来度量</p>
<h4><a id="%E4%BA%8B%E5%90%8E%E7%BB%9F%E8%AE%A1%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>事后统计法</h4>
<p>算法设计完成后通过实际运行统计时间</p>
<h4><a id="%E4%BA%8B%E5%89%8D%E5%88%86%E6%9E%90%E4%BC%B0%E7%AE%97%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>事前分析估算法</h4>
<p>一般情况下，算法中基本语句重复执行的次数是问题规模<code>n</code>的某个函数<code>f(n)</code>，记作：</p>
<pre class="line-numbers"><code class="language-plain_text">T(n) = O(f(n))
</code></pre>
<p>它表示随问题规模<code>n</code>的增大，算法执行时间的增长率和<code>f(n)</code>的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度</p>
<p><strong>T：</strong> 称为算法的渐进时间复杂度<br />
<strong>O：</strong> 算法具体功能的变化趋势</p>
<table>
<thead>
<tr>
<th>常数阶</th>
<th>对数阶</th>
<th>线性阶</th>
<th>线性对数阶</th>
<th>平方阶</th>
<th>立方阶</th>
<th>...</th>
<th>K次方阶</th>
<th>指数阶</th>
</tr>
</thead>
<tbody>
<tr>
<td>O(1)</td>
<td>O(log<sub>2</sub>n)</td>
<td>O(n)</td>
<td>O(n log<sub>2</sub>n)</td>
<td>O(n<sup>2</sup>)</td>
<td>O(n<sup>3</sup>)</td>
<td>...</td>
<td>O(n<sup>k</sup>)</td>
<td>O(2<sup>n</sup>)</td>
</tr>
</tbody>
</table>
<h5><a id="%E6%9C%80%E5%A5%BD%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>最好时间复杂度</h5>
<p>算法在最好情况下的时间复杂度，指算法计算量可能达到的最小值</p>
<h5><a id="%E6%9C%80%E5%9D%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>最坏时间复杂度</h5>
<p>算法在最坏情况下的时间复杂度，指算法计算量可能达到的最大值</p>
<h5><a id="%E5%B9%B3%E5%9D%87%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>平均时间复杂度</h5>
<p>算法在所有可能的情况下，按照输入示例以等概率出现时，算法计算量的加权平均值</p>
<h3><a id="q4%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%A6%82%E4%BD%95%E8%A1%A8%E7%A4%BA" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Q4 空间复杂度如何表示</h3>
<p>类似于算法的时间复杂度，采用渐进空间复杂度作为算法所需存储空间的度量，简称空间复杂度，也是问题规模<code>n</code>的函数，记作</p>
<pre class="line-numbers"><code class="language-plain_text">S(n) = O(f(n))
</code></pre>
<ul>
<li>
<p>一般情况下，一个程序在机器上执行时，除了需要寄存本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的辅助存储空间</p>
</li>
<li>
<p>其中，对于输入数据所占的具体存储量取决于问题本身，与算法无关，只需分析该算法在实现时所需要的辅助空间，用<code>S(n)</code>表示</p>
</li>
</ul>

				</article>
				<div class="comments-wrap">
					<div class="share-comments">
						

						

						
					</div>
				</div><!-- end comments wrap -->
			</div>
		</div><!-- end columns -->
	</div><!-- end container -->
</section>  









<script>!function(){var deflate=function(){var e,n,r,t,i,o,a,f,d,l,c,u,h,w,m,s,g,p,y,_,v,x,A,C,b,V,E,z,I,S,B,G,L,M,O,D,N,q,T,k,H,U,j,F,P,R,J,K,Q,W,X,Y,Z,$,ee,ne,re=32768,te=0,ie=1,oe=2,ae=6,fe=!0,de=32768,le=64,ce=8192,ue=2*re,he=3,we=258,me=16,se=8192,ge=se,pe=8192,ye=pe-1,_e=re-1,ve=0,xe=4096,Ae=we+he+1,Ce=re-Ae,be=1,Ve=15,Ee=7,ze=29,Ie=256,Se=256,Be=Ie+1+ze,Ge=30,Le=19,Me=16,Oe=17,De=18,Ne=2*Be+1,qe=parseInt((13+he-1)/he),Te=null;function ke(){this.fc=0,this.dl=0}function He(){this.dyn_tree=null,this.static_tree=null,this.extra_bits=null,this.extra_base=0,this.elems=0,this.max_length=0,this.max_code=0}function Ue(e,n,r,t){this.good_length=e,this.max_lazy=n,this.nice_length=r,this.max_chain=t}var je=[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0],Fe=[0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13],Pe=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7],Re=[16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15],Je=[new Ue(0,0,0,0),new Ue(4,4,8,4),new Ue(4,5,16,8),new Ue(4,6,32,32),new Ue(4,4,16,16),new Ue(8,16,32,32),new Ue(8,16,128,128),new Ue(8,32,128,256),new Ue(32,128,258,1024),new Ue(32,258,258,4096)];function Ke(){var n;return null!=e?(n=e,e=e.next):n=new function(){this.next=null,this.len=0,this.ptr=new Array(ce),this.off=0},n.next=null,n.len=n.off=0,n}function Qe(e){return c[re+e]}function We(e,n){return c[re+e]=n}function Xe(e){Te[o+i++]=e,o+i==ce&&function(){if(0!=i){var e,t;for(e=Ke(),null==n?n=r=e:r=r.next=e,e.len=i-o,t=0;t<e.len;t++)e.ptr[t]=Te[o+t];i=o=0}}()}function Ye(e){e&=65535,o+i<ce-2?(Te[o+i++]=255&e,Te[o+i++]=e>>>8):(Xe(255&e),Xe(e>>>8))}function Ze(){m=(m<<qe^255&f[v+he-1])&ye,s=Qe(m),c[v&_e]=s,We(m,v)}function $e(e,n){_n(n[e].fc,n[e].dl)}function en(e){return 255&(e<256?F[e]:F[256+(e>>7)])}function nn(e,n,r){return e[n].fc<e[r].fc||e[n].fc==e[r].fc&&U[n]<=U[r]}function rn(e,n,r){var t;for(t=0;t<r&&ne<ee.length;t++)e[n+t]=255&ee.charCodeAt(ne++);return t}function tn(e){var n,r,t=b,i=v,o=_,a=v>Ce?v-Ce:ve,d=v+we,l=f[i+o-1],u=f[i+o];_>=z&&(t>>=2);do{if(f[(n=e)+o]==u&&f[n+o-1]==l&&f[n]==f[i]&&f[++n]==f[i+1]){i+=2,n++;do{}while(f[++i]==f[++n]&&f[++i]==f[++n]&&f[++i]==f[++n]&&f[++i]==f[++n]&&f[++i]==f[++n]&&f[++i]==f[++n]&&f[++i]==f[++n]&&f[++i]==f[++n]&&i<d);if(r=we-(d-i),i=d-we,r>o){if(x=e,o=r,fe){if(r>=we)break}else if(r>=I)break;l=f[i+o-1],u=f[i+o]}}}while((e=c[e&_e])>a&&0!=--t);return o}function on(){var e,n,r=ue-C-v;if(-1==r)r--;else if(v>=re+Ce){for(e=0;e<re;e++)f[e]=f[e+re];for(x-=re,v-=re,w-=re,e=0;e<pe;e++)We(e,(n=Qe(e))>=re?n-re:ve);for(e=0;e<re;e++)n=c[e],c[e]=n>=re?n-re:ve;r+=re}A||((e=rn(f,v+C,r))<=0?A=!0:C+=e)}function an(){A||(u=0,h=0,function(){var e,n,r,t,i;if(0!=L[0].dl)return;for(O.dyn_tree=S,O.static_tree=G,O.extra_bits=je,O.extra_base=Ie+1,O.elems=Be,O.max_length=Ve,O.max_code=0,D.dyn_tree=B,D.static_tree=L,D.extra_bits=Fe,D.extra_base=0,D.elems=Ge,D.max_length=Ve,D.max_code=0,N.dyn_tree=M,N.static_tree=null,N.extra_bits=Pe,N.extra_base=0,N.elems=Le,N.max_length=Ee,N.max_code=0,r=0,t=0;t<ze-1;t++)for(P[t]=r,e=0;e<1<<je[t];e++)j[r++]=t;for(j[r-1]=t,i=0,t=0;t<16;t++)for(R[t]=i,e=0;e<1<<Fe[t];e++)F[i++]=t;for(i>>=7;t<Ge;t++)for(R[t]=i<<7,e=0;e<1<<Fe[t]-7;e++)F[256+i++]=t;for(n=0;n<=Ve;n++)q[n]=0;e=0;for(;e<=143;)G[e++].dl=8,q[8]++;for(;e<=255;)G[e++].dl=9,q[9]++;for(;e<=279;)G[e++].dl=7,q[7]++;for(;e<=287;)G[e++].dl=8,q[8]++;for(un(G,Be+1),e=0;e<Ge;e++)L[e].dl=5,L[e].fc=vn(e,5);ln()}(),function(){var e;for(e=0;e<pe;e++)c[re+e]=0;if(V=Je[E].max_lazy,z=Je[E].good_length,fe||(I=Je[E].nice_length),b=Je[E].max_chain,v=0,w=0,(C=rn(f,0,2*re))<=0)return A=!0,void(C=0);for(A=!1;C<Ae&&!A;)on();for(m=0,e=0;e<he-1;e++)m=(m<<qe^255&f[e])&ye}(),n=null,i=0,o=0,E<=3?(_=he-1,y=0):(y=he-1,p=0),a=!1)}function fn(e,r,i){var o;return t||(an(),t=!0,0!=C)?(o=dn(e,r,i))==i?i:a?o:(E<=3?function(){for(;0!=C&&null==n;){var e;if(Ze(),s!=ve&&v-s<=Ce&&(y=tn(s))>C&&(y=C),y>=he)if(e=gn(v-x,y-he),C-=y,y<=V){y--;do{v++,Ze()}while(0!=--y);v++}else v+=y,y=0,m=((m=255&f[v])<<qe^255&f[v+1])&ye;else e=gn(0,255&f[v]),C--,v++;for(e&&(sn(0),w=v);C<Ae&&!A;)on()}}():function(){for(;0!=C&&null==n;){if(Ze(),_=y,g=x,y=he-1,s!=ve&&_<V&&v-s<=Ce&&((y=tn(s))>C&&(y=C),y==he&&v-x>xe&&y--),_>=he&&y<=_){var e;e=gn(v-1-g,_-he),C-=_-1,_-=2;do{v++,Ze()}while(0!=--_);p=0,y=he-1,v++,e&&(sn(0),w=v)}else 0!=p?(gn(0,255&f[v-1])&&(sn(0),w=v),v++,C--):(p=1,v++,C--);for(;C<Ae&&!A;)on()}}(),0==C&&(0!=p&&gn(0,255&f[v-1]),sn(1),a=!0),o+dn(e,o+r,i-o)):(a=!0,0)}function dn(r,t,a){var f,d,l,c;for(f=0;null!=n&&f<a;){for((d=a-f)>n.len&&(d=n.len),l=0;l<d;l++)r[t+f+l]=n.ptr[n.off+l];var u;if(n.off+=d,n.len-=d,f+=d,0==n.len)u=n,n=n.next,(c=u).next=e,e=c}if(f==a)return f;if(o<i){for((d=a-f)>i-o&&(d=i-o),l=0;l<d;l++)r[t+f+l]=Te[o+l];f+=d,i==(o+=d)&&(i=o=0)}return f}function ln(){var e;for(e=0;e<Be;e++)S[e].fc=0;for(e=0;e<Ge;e++)B[e].fc=0;for(e=0;e<Le;e++)M[e].fc=0;S[Se].fc=1,Z=$=0,K=Q=W=0,X=0,Y=1}function cn(e,n){for(var r=T[n],t=n<<1;t<=k&&(t<k&&nn(e,T[t+1],T[t])&&t++,!nn(e,r,T[t]));)T[n]=T[t],n=t,t<<=1;T[n]=r}function un(e,n){var r,t,i=new Array(Ve+1),o=0;for(r=1;r<=Ve;r++)o=o+q[r-1]<<1,i[r]=o;for(t=0;t<=n;t++){var a=e[t].dl;0!=a&&(e[t].fc=vn(i[a]++,a))}}function hn(e){var n,r,t=e.dyn_tree,i=e.static_tree,o=e.elems,a=-1,f=o;for(k=0,H=Ne,n=0;n<o;n++)0!=t[n].fc?(T[++k]=a=n,U[n]=0):t[n].dl=0;for(;k<2;){var d=T[++k]=a<2?++a:0;t[d].fc=1,U[d]=0,Z--,null!=i&&($-=i[d].dl)}for(e.max_code=a,n=k>>1;n>=1;n--)cn(t,n);do{n=T[be],T[be]=T[k--],cn(t,be),r=T[be],T[--H]=n,T[--H]=r,t[f].fc=t[n].fc+t[r].fc,U[n]>U[r]+1?U[f]=U[n]:U[f]=U[r]+1,t[n].dl=t[r].dl=f,T[be]=f++,cn(t,be)}while(k>=2);T[--H]=T[be],function(e){var n,r,t,i,o,a,f=e.dyn_tree,d=e.extra_bits,l=e.extra_base,c=e.max_code,u=e.max_length,h=e.static_tree,w=0;for(i=0;i<=Ve;i++)q[i]=0;for(f[T[H]].dl=0,n=H+1;n<Ne;n++)(i=f[f[r=T[n]].dl].dl+1)>u&&(i=u,w++),f[r].dl=i,r>c||(q[i]++,o=0,r>=l&&(o=d[r-l]),a=f[r].fc,Z+=a*(i+o),null!=h&&($+=a*(h[r].dl+o)));if(0!=w){do{for(i=u-1;0==q[i];)i--;q[i]--,q[i+1]+=2,q[u]--,w-=2}while(w>0);for(i=u;0!=i;i--)for(r=q[i];0!=r;)(t=T[--n])>c||(f[t].dl!=i&&(Z+=(i-f[t].dl)*f[t].fc,f[t].fc=i),r--)}}(e),un(t,a)}function wn(e,n){var r,t,i=-1,o=e[0].dl,a=0,f=7,d=4;for(0==o&&(f=138,d=3),e[n+1].dl=65535,r=0;r<=n;r++)t=o,o=e[r+1].dl,++a<f&&t==o||(a<d?M[t].fc+=a:0!=t?(t!=i&&M[t].fc++,M[Me].fc++):a<=10?M[Oe].fc++:M[De].fc++,a=0,i=t,0==o?(f=138,d=3):t==o?(f=6,d=3):(f=7,d=4))}function mn(e,n){var r,t,i=-1,o=e[0].dl,a=0,f=7,d=4;for(0==o&&(f=138,d=3),r=0;r<=n;r++)if(t=o,o=e[r+1].dl,!(++a<f&&t==o)){if(a<d)do{$e(t,M)}while(0!=--a);else 0!=t?(t!=i&&($e(t,M),a--),$e(Me,M),_n(a-3,2)):a<=10?($e(Oe,M),_n(a-3,3)):($e(De,M),_n(a-11,7));a=0,i=t,0==o?(f=138,d=3):t==o?(f=6,d=3):(f=7,d=4)}}function sn(e){var n,r,t,i,o;if(i=v-w,J[W]=X,hn(O),hn(D),t=function(){var e;for(wn(S,O.max_code),wn(B,D.max_code),hn(N),e=Le-1;e>=3&&0==M[Re[e]].dl;e--);return Z+=3*(e+1)+5+5+4,e}(),(r=$+3+7>>3)<=(n=Z+3+7>>3)&&(n=r),i+4<=n&&w>=0)for(_n((te<<1)+e,3),xn(),Ye(i),Ye(~i),o=0;o<i;o++)Xe(f[w+o]);else r==n?(_n((ie<<1)+e,3),pn(G,L)):(_n((oe<<1)+e,3),function(e,n,r){var t;for(_n(e-257,5),_n(n-1,5),_n(r-4,4),t=0;t<r;t++)_n(M[Re[t]].dl,3);mn(S,e-1),mn(B,n-1)}(O.max_code+1,D.max_code+1,t+1),pn(S,B));ln(),0!=e&&xn()}function gn(e,n){if(l[K++]=n,0==e?S[n].fc++:(e--,S[j[n]+Ie+1].fc++,B[en(e)].fc++,d[Q++]=e,X|=Y),Y<<=1,0==(7&K)&&(J[W++]=X,X=0,Y=1),E>2&&0==(4095&K)){var r,t=8*K,i=v-w;for(r=0;r<Ge;r++)t+=B[r].fc*(5+Fe[r]);if(t>>=3,Q<parseInt(K/2)&&t<parseInt(i/2))return!0}return K==se-1||Q==ge}function pn(e,n){var r,t,i,o,a=0,f=0,c=0,u=0;if(0!=K)do{0==(7&a)&&(u=J[c++]),t=255&l[a++],0==(1&u)?$e(t,e):($e((i=j[t])+Ie+1,e),0!=(o=je[i])&&_n(t-=P[i],o),$e(i=en(r=d[f++]),n),0!=(o=Fe[i])&&_n(r-=R[i],o)),u>>=1}while(a<K);$e(Se,e)}var yn=16;function _n(e,n){h>yn-n?(Ye(u|=e<<h),u=e>>yn-h,h+=n-yn):(u|=e<<h,h+=n)}function vn(e,n){var r=0;do{r|=1&e,e>>=1,r<<=1}while(--n>0);return r>>1}function xn(){h>8?Ye(u):h>0&&Xe(u),u=0,h=0}return function(i,o){var a,u;ee=i,ne=0,void 0===o&&(o=ae),function(i){var o;if(i?i<1?i=1:i>9&&(i=9):i=ae,E=i,t=!1,A=!1,null==Te){for(e=n=r=null,Te=new Array(ce),f=new Array(ue),d=new Array(ge),l=new Array(de+le),c=new Array(1<<me),S=new Array(Ne),o=0;o<Ne;o++)S[o]=new ke;for(B=new Array(2*Ge+1),o=0;o<2*Ge+1;o++)B[o]=new ke;for(G=new Array(Be+2),o=0;o<Be+2;o++)G[o]=new ke;for(L=new Array(Ge),o=0;o<Ge;o++)L[o]=new ke;for(M=new Array(2*Le+1),o=0;o<2*Le+1;o++)M[o]=new ke;O=new He,D=new He,N=new He,q=new Array(Ve+1),T=new Array(2*Be+1),U=new Array(2*Be+1),j=new Array(we-he+1),F=new Array(512),P=new Array(ze),R=new Array(Ge),J=new Array(parseInt(se/8))}}(o);for(var h=new Array(1024),w=[];(a=fn(h,0,h.length))>0;){var m=new Array(a);for(u=0;u<a;u++)m[u]=String.fromCharCode(h[u]);w[w.length]=m.join("")}return ee=null,w.join("")}}();function encode64(e){for(r="",i=0;i<e.length;i+=3)i+2==e.length?r+=append3bytes(e.charCodeAt(i),e.charCodeAt(i+1),0):i+1==e.length?r+=append3bytes(e.charCodeAt(i),0,0):r+=append3bytes(e.charCodeAt(i),e.charCodeAt(i+1),e.charCodeAt(i+2));return r}function append3bytes(e,n,t){return c1=e>>2,c2=(3&e)<<4|n>>4,c3=(15&n)<<2|t>>6,c4=63&t,r="",r+=encode6bit(63&c1),r+=encode6bit(63&c2),r+=encode6bit(63&c3),r+=encode6bit(63&c4),r}function encode6bit(e){return e<10?String.fromCharCode(48+e):(e-=10)<26?String.fromCharCode(65+e):(e-=26)<26?String.fromCharCode(97+e):0==(e-=26)?"-":1==e?"_":"?"}function insertAfter(e,n){e.parentNode.insertBefore(n,e.nextSibling)}var mwebChartEleId="mweb-chart-ele-",glNumber=0;function drawOldSeq(e,n){Diagram.parse(n).drawSVG(e,{theme:"simple"})}function drawOldFlow(e,n){flowchart.parse(n).drawSVG(e)}function drawMermaid(e,n){var r=document.getElementById(e);r.className="mermaid",r.innerHTML=n}function drawPlantUML(e,n){var r=document.getElementById(e),t=unescape(encodeURIComponent(n)),i="https://www.plantuml.com/plantuml/svg/"+encode64(deflate(t,9));r.innerHTML='<a target="_blank" href="'+i+'"><img src="'+i+'" /></a>'}function drawViz_circo(e,n){(new Viz).renderSVGElement(n,{engine:"circo"}).then(function(n){document.getElementById(e).appendChild(n)})}function drawViz_dot(e,n){(new Viz).renderSVGElement(n,{engine:"dot"}).then(function(n){document.getElementById(e).appendChild(n)})}function drawViz_fdp(e,n){(new Viz).renderSVGElement(n,{engine:"fdp"}).then(function(n){document.getElementById(e).appendChild(n)})}function drawViz_neato(e,n){(new Viz).renderSVGElement(n,{engine:"neato"}).then(function(n){document.getElementById(e).appendChild(n)})}function drawViz_osage(e,n){(new Viz).renderSVGElement(n,{engine:"osage"}).then(function(n){document.getElementById(e).appendChild(n)})}function drawViz_twopi(e,n){(new Viz).renderSVGElement(n,{engine:"twopi"}).then(function(n){document.getElementById(e).appendChild(n)})}function drawECharts(eleIID,txt){var ele=document.getElementById(eleIID);try{eval(txt);var myoption=option;myoption.animation=!1,void 0!==myoption.width?ele.style.width=myoption.width+10+"px":ele.style.width="100%",void 0!==myoption.height?ele.style.height=myoption.height+10+"px":ele.style.height="350px";var myChart=echarts.init(ele);myChart.setOption(myoption)}catch(e){}}var init=function(){var e=[[".language-plantuml",drawPlantUML]];"undefined"!=typeof Diagram&&e.push([".language-sequence",drawOldSeq]),"undefined"!=typeof flowchart&&e.push([".language-flow",drawOldFlow]),"undefined"!=typeof mermaid&&e.push([".language-mermaid",drawMermaid]),"undefined"!=typeof Viz&&(e.push([".language-circo",drawViz_circo]),e.push([".language-dot",drawViz_dot]),e.push([".language-fdp",drawViz_fdp]),e.push([".language-neato",drawViz_neato]),e.push([".language-osage",drawViz_osage]),e.push([".language-twopi",drawViz_twopi])),"undefined"!=typeof echarts&&e.push([".language-echarts",drawECharts]);for(var n=0;n<e.length;n++)for(var r=e[n][0],t=e[n][1],i=document.querySelectorAll(r),o=0;o<i.length;o++){var a=i[o],f=a.innerText||a.textContent;a=a.parentElement;var d=document.createElement("div"),l=mwebChartEleId+glNumber;glNumber++,d.innerHTML='<div id="'+l+'"></div>',insertAfter(a,d),a.parentElement.removeChild(a),t(l,f)}"undefined"!=typeof mermaid&&mermaid.initialize({startOnLoad:!0})};document.addEventListener("DOMContentLoaded",function(e){init()})}();</script>



<link rel="stylesheet" type="text/css"
	href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/4.7.0/css/font-awesome.min.css" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/mermaid/8.4.3/mermaid.min.js"></script>




<script src="asset/prism.js"></script>









</body>

</html>